import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };

    public List<List<Integer>> levelOrder(Node root) {
        /**
         * N叉树的层序遍历
         * 解法：
         *  直接使用bfs算法进行操作，但为了记录返回值，故每层进行记录
         * 操作步骤：
         *  1，初始化
         *  2，记录当前队列元素个数
         *  3，出队当前层，记录值，并将子节点入队
         *  4，循环，直至队列为空*/
        // 1 预处理
        List<List<Integer>> retArray = new LinkedList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        // 2 BFS（分层）
        while(!queue.isEmpty()) {
            // -1 记录本层元素个数
            int l = queue.size();
            List<Integer> tempArray = new LinkedList<>();

            // -2 出本层
            for(int i = 0; i < l; i++) {
                Node cur = queue.poll();
                if(cur == null) {
                    continue;
                }
                tempArray.add(cur.val);
                for(Node e: cur.children) {
                    queue.offer(e);
                }
            }

            // -3 整合记录
            if(!tempArray.isEmpty()) {
                retArray.add(tempArray);
            }
        }

        // 3 返回值
        return retArray;
    }


}
